package com.zbxx.leetcode.recursion;


/**
 * 剑指offer 51 逆序对
 *
 * @author wanrj
 * @date 2023/6/13
 */
public class reversepairs {

    public int reversePairs(int[] nums) {
        int temp[] = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            temp[i] = nums[i];
        }
        return mergerSort(nums, 0, nums.length - 1, new int[nums.length]);
    }


    public int mergerSort(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int lc = mergerSort(nums, left, mid, temp);
        int rc = mergerSort(nums, mid + 1, right, temp);
        if (nums[mid] <= nums[mid + 1]) {
            return lc + rc;
        }
        int merge = merge(nums, left, mid, right, temp);
        return lc + rc + merge;
    }


    public int merge(int[] nums, int left, int mid, int right, int temp[]) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int count = 0;
        for (int k = left; k <= right; k++) {

            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;
                count += (mid - i + 1);
            }
        }
        return count;
    }


}
